<html>
<head><meta charset="utf-8"><title>try_sort · t-libs · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/index.html">t-libs</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html">try_sort</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="226691220"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226691220" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226691220">(Feb 17 2021 at 17:13)</a>:</h4>
<p>It seems there aren't any good methods for fallible sorting, with two (to me) compelling use-cases:</p>
<ul>
<li>PartialOrd where you want to bail out early on, EG, NaN-like values with an <code>Err()</code> or <code>None</code></li>
<li>Values that rely on some external information which may or may not itself be present</li>
</ul>
<p>It seems there should be some kind of <code>try_sort_by&lt;R: Try&lt;Ok = Ordering&gt;, F: FnMut(&amp;T, &amp;T) -&gt; R&gt;(&amp;mut self, compare: F) -&gt; Option&lt;R::Error&gt;</code> (and similar <code>try_sort_by_key</code>, <code>try_sort_unstable*</code>). Would implementations of these functions have a chance of landing as an unstable API?</p>



<a name="226691363"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226691363" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Thom Chiovoloni <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226691363">(Feb 17 2021 at 17:14)</a>:</h4>
<p>what state would it leave the input if it failed?</p>



<a name="226691644"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226691644" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226691644">(Feb 17 2021 at 17:16)</a>:</h4>
<p>That's the biggest question. Current sort and sort_unstable functions just say that if the ordering isn't total, the result is undefined. I think 'unchanged' is impractical, so I think 'undefined' is also fine here</p>



<a name="226691730"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226691730" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226691730">(Feb 17 2021 at 17:17)</a>:</h4>
<p>The result after a failed sort should still be usable, but not meaningfully sorted</p>



<a name="226691771"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226691771" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226691771">(Feb 17 2021 at 17:17)</a>:</h4>
<p>Given that it's safe and the available bounds, I think the only practical implementation would be "it's some permutation of the original".</p>



<a name="226691952"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226691952" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226691952">(Feb 17 2021 at 17:18)</a>:</h4>
<p>One of the problems with adding another dimension here is that it's at least 6 more methods.</p>



<a name="226692085"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226692085" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Thom Chiovoloni <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226692085">(Feb 17 2021 at 17:19)</a>:</h4>
<p>it would be arguably worth it for float sorting, although i suspect the performance would be hard to make as good...</p>



<a name="226692103"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226692103" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226692103">(Feb 17 2021 at 17:19)</a>:</h4>
<p>Does this really need fallible comparators?  It seems like threading that all the way through the implementation would be a pain, and could have strange effects on the codegen and thus perf.</p>



<a name="226692111"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226692111" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226692111">(Feb 17 2021 at 17:19)</a>:</h4>
<p>5, I think. <code>sort_by</code>, <code>sort_by_key</code>, <code>sort_by_cached_key</code>, then the first two again as unstable</p>



<a name="226692198"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226692198" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226692198">(Feb 17 2021 at 17:20)</a>:</h4>
<p>Note that for float sorting there's <code>f32::total_cmp</code>, which works great for sorting.</p>



<a name="226692288"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226692288" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Thom Chiovoloni <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226692288">(Feb 17 2021 at 17:21)</a>:</h4>
<p>yeah</p>



<a name="226692304"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226692304" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Thom Chiovoloni <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226692304">(Feb 17 2021 at 17:21)</a>:</h4>
<p>if that ever stabilizes...</p>



<a name="226693143"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693143" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693143">(Feb 17 2021 at 17:26)</a>:</h4>
<p>The thing I was pondering, for your proposal, is whether for the "external information" one that ever makes sense for anything <em>but</em> <code>_by_cached_key</code>.</p>



<a name="226693173"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693173" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693173">(Feb 17 2021 at 17:27)</a>:</h4>
<p>Fair. This was more inspired by cases for user-defined types, and my second bullet-point where the issue isn't as much the ordering of the values, but that the sort itself may fail. Which then begs a performance question, but I think computing-as-you-go for EG filesystem access is no less efficient than pre-computing, and much nicer to read.</p>



<a name="226693240"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693240" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693240">(Feb 17 2021 at 17:27)</a>:</h4>
<p>And hm, yeah. For what I just said, you would <em>always</em> want to cache the key performance wise, unless you were somehow worried about it changing mid-sort? Which would probably be more an issue with design at that point</p>



<a name="226693338"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693338" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693338">(Feb 17 2021 at 17:28)</a>:</h4>
<p>You arguably can't even change the key mid-sort, because that would almost certainly violate transitivity.</p>



<a name="226693375"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693375" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693375">(Feb 17 2021 at 17:28)</a>:</h4>
<p>So I was thinking along the lines of "what if there was just <code>sort_by_fallible_key</code>?"</p>



<a name="226693416"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693416" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693416">(Feb 17 2021 at 17:28)</a>:</h4>
<p>Yeah. So only allowing caching would prevent an easy to make data race error</p>



<a name="226693425"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693425" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693425">(Feb 17 2021 at 17:29)</a>:</h4>
<p>Where the key function is <code>&amp;T -&gt; Result&lt;K, E&gt;</code>.</p>



<a name="226693496"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693496" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693496">(Feb 17 2021 at 17:29)</a>:</h4>
<p>Then <code>sort_by_fallible_key</code> is <code>-&gt; Result&lt;(), E&gt;</code>, and leave it unpermuted if any of the key extractors fail.</p>



<a name="226693766"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693766" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693766">(Feb 17 2021 at 17:31)</a>:</h4>
<p>Hm, could work. I like the genericity of the original, but this would probably be nicer on codegen and allow that invariant</p>



<a name="226693791"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693791" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Thom Chiovoloni <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693791">(Feb 17 2021 at 17:31)</a>:</h4>
<p>there are a lot of cases where you can't use <code>sort_by.*_key</code> where you could use <code>sort_by</code>, also i think the "external information" case is probably not the most common, and it seems unfortunate to force the inefficiency of precomputing on them</p>



<a name="226693969"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226693969" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226693969">(Feb 17 2021 at 17:32)</a>:</h4>
<p>And it's only one new method, not 6+.  And it doesn't require touching the internals of the sorting algorithms.</p>



<a name="226694502"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226694502" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226694502">(Feb 17 2021 at 17:35)</a>:</h4>
<p>Hmm. I kind of agree with Thom, but I'm trying to consider how to allow both the likely more common and the less, without API bloat. I think 2 methods might be okay, but it would be weird for them to look symmetric but have wildly different signatures/invariants</p>



<a name="226694945"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226694945" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226694945">(Feb 17 2021 at 17:38)</a>:</h4>
<p><code>try_sort_by</code> and <code>sort_fallible_key</code> wouldn't look symmetric, it might raise "why not the rest of the sort methods", but it at least covers the two cases. Regains the sorting internals issue though</p>



<a name="226695260"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/try_sort/near/226695260" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> CraftSpider <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/try_sort.html#226695260">(Feb 17 2021 at 17:40)</a>:</h4>
<p>I'll probably think on it some more. Might open a PR if you think any variant of this API might be worth adding, and do more bikeshedding once the implementation costs are clearer?</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>